1. Field of the Invention
The invention relates to systems and methods that facilitate efficient storage of data in a buffer.
2. Related Art
Data packet switches receive data packets on a number of input ports, and are configured to route individual or groups of data packets to one or more output ports, based on their source and/or destination address. Packet switches typically include a packet buffer in order to hold received data packets until they are scheduled to be transmitted on outgoing links. A packet buffer generally includes several buffer banks that can store a number of entries. In some implementations, the individual buffer banks are able to execute a read access or a write access each buffer cycle, but not both. This limitation in the buffer bank capability can result in read/write conflicts, which are situations where an individual bank receives request to both read and write during a single read/write cycle and cannot perform both. Read/write conflicts limit the ability of a buffer to use all of its available physical address space, and therefore is undesirable.
For instance, consider the simple example of a buffer that consists of two banks such as that depicted in FIGS. 1A and 1B. As shown in FIG. 1A, buffer 102 comprises buffer bank A 104 and buffer bank B 106. Buffer bank A 104 is entirely filled and buffer bank B 106 has a single entry 108 stored in it. Accordingly, the buffer 102 is only slightly more than half full, but has an asymmetric (i.e., uneven) data distribution. FIG. 1A depicts a first example where buffer 102 receives a read request to read data 110 stored in bank A 104 and a write request to write data 112. In this situation, both requests can be executed; bank A 104 only has a single read request for data 110 and bank B 106 has ample space to store data 112 and no other read/write operations to perform that cycle. In this first example, buffer 102 has no read/write conflicts.
FIG. 1B depicts a second, more problematic example using the same buffer 102 as an example. In this second example, the buffer 102 receives a read request for data 108, which is stored in buffer bank B 106. Additionally, the buffer receives a request to write data 112. While the buffer can read data 108, it cannot write data 112 anywhere during the cycle because bank A 104 is full and bank B 106 must perform a read operation during the cycle, which precludes it from also writing. This situation constitutes a read/write conflict because, despite having sufficient space, bank B 106 cannot write data 112. Thus, as can be seen, the read/write conflict causes the buffer 102 to behave as if it is full even though it is nearly half empty.
One solution to the kind of problem outlined above would be to add extra buffer banks to a buffer to accommodate this situation. For instance, continuing with the example scenario depicted in FIGS. 1A and 1B, a third buffer bank C 114 could be added to buffer 102. Thus, in the event that the problematic second example depicted in FIG. 1B occurs, the buffer 102 could simply write the data 112 to bank C 114. This solution, however, requires the addition of an extra bank (or banks in many cases), which incurs extra direct and indirect costs. For instance, extra banks require additional overhead, but fail to provide any direct value because the capacity of the buffer 102 is still the capacity of banks A and B. Additionally, the extra banks require corresponding data structures to control their allocation and accounting. The solution of adding extra banks, therefore, leaves something to be desired.